COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂25-Oct-86  1410	KMP@STONY-BROOK.SCRC.Symbolics.COM 	Your turn
C00023 ENDMK
C⊗;
∂25-Oct-86  1410	KMP@STONY-BROOK.SCRC.Symbolics.COM 	Your turn
Received: from SCRC-STONY-BROOK.ARPA by SAIL.STANFORD.EDU with TCP; 25 Oct 86  14:10:30 PDT
Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 142728; Sat 25-Oct-86 17:10:19 EDT
Date: Sat, 25 Oct 86 17:08 EDT
From: Kent M Pitman <KMP@SCRC-STONY-BROOK.ARPA>
Subject: Your turn
To: RPG@SU-AI.ARPA
cc: KMP@SCRC-STONY-BROOK.ARPA
Message-ID: <861025170843.9.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

Ok, I've exhausted all the time I have to work on this today and you
should have a go at it before it gets too well-formed anyway. Please feel
free to fill out things or change the order or wording. Obviously I have
a saved draft and can compare anything you send back with it to find out
what you've done.

I started off by assuming there would be two parts to section 3 --
advantages and disadvantages, but that looked like it'd be too hard on
the reader who would feel like he'd seen two separate documents, so I
decided to merge them and assume that the arguments would be more
intimately intertwined. You can change it back if you disagree.

I'm using a stripped down form of Scribe that Zmacs understands with the
m-X Format Buffer command, so if you have a 3600 around, that's the
recommended way to get this typed out. c-U m-X Format Buffer will let
you output it to a hardcopy device. Presumably Scribe will also mostly
like it if I didn't screw up and do @foo(@bar(...)) instead of
@foo(@bar[...])  so that it's stupid little parser can deal. If the formatter
is a problem, change it to what you like. I'm sure I can change it back
easily enough while I play with it.

I'd like to get this back in a week or so. Good luck, and drop me a line
if you have any questions about the parts that aren't fully detailed...

-----Text of Paper Follows-----
@center(@b[Issues of Separation in Function Cells and Value Cells])

@center(@b[by RPG and KMP, etc.])

@b(1. Introduction)

Motivation ... The Europeans in [what?] have suggested that we should
[something specific goes here].

The Common Lisp community is currently studying the issue. Here are some
questions we might want to answer:
 Is it technically feasible to change things?
 What is the cost/benefit of making the change?
 What is the cost/benefit of having made the change?

Before attempting to make any decision on the subject, the Common Lisp
community felt it important to clearly document both sides of the issue
in an unbiased way.

@b(2. Background)

[Perhaps some text here about how and why the separation arose originally
in case it was for different reasons than why it survived. Perhaps, too,
some text about what happened in languages like Scheme where the separation
did not arise.]

@b(3. Issues)

@b(3.1 Notational Simplicity)

Many people believe that having the function position be evaluated
differently than the argument positions in Lisp is very inelegant.

This feature has the indirect effect of making the notation more
complicated in order to allow two things -- looking up a function
to call using the rules for variable evaluation and looking up an
argument to pass using the rules for functional evaluation.

To call a function which is the value of a variable (or the result
of some other normally evaluated expression), you currently must use
the @t(FUNCALL) function. For example, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (FUNCALL F X)))
@End(Example)
If functions and arguments were evaluated the same, one might write:
@Begin(Example)
(DEFUN MAPC-1 (F L) (DOLIST (X L) (F X)))
@End(Example)

To pass an argument which is obtained by the rules of functional
evaluation, you currently must use the @t(FUNCTION) special form.
For example, one might write:
@Begin(Example)
(MAPC #'PRINT '(A B C D))
@End(Example)
If functions and arguments were evaluated the same, one might write:
@Begin(Example)
(MAPC PRINT '(A B C D))
@End(Example)

Probably few people would deny that the syntax resulting from the this
change would make the language appear better visually. If the issue were
being decided purely on the basis of cosmetics, probably few people
would oppose the change. Resistance to change by some members of the
Common Lisp community is generally based in the implications of the
change on current and future code, rather than in some claim that there
is no visual appeal to this simpler syntax.

@b(3.2 Multiple denotations for a single name)

Some people find it less confusing to have a single meaning for a name.
Fewer meanings mean less to remember.

For example, suppose you have defined a function @t(F) as:
@Begin(Example)
(DEFUN F (X) (+ X 1))
@End(Example)
Then suppose you are writing a new function @t(G) and you want it to
take a functional parameter @t(F) which it is to apply to its other argument.
Suppose you wrote:
@Begin(Example)
(DEFUN G (F) (F 3))
@End(Example)
Issues of defined program semantics aside, it's obvious that the programmer
who wrote this piece of code meant to call the function named by the formal
parameter @t(F) on the argument @t(3). The semantics of present day Common 
Lisp are more complicated because they define this expression to involve
a globally defined function named @t(F) which the programmer is trying to call 
and a local parameter named @t(F) which the programmer is trying to ignore.

Unfortunately, not all situations are as clear cut as this. For example, 
in the following example:
@Begin(Example)
(DEFUN PRINT-SQRTS (LIST)
  (DOLIST (ELEMENT LIST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)
In this example, there are three uses of the name @t(LIST). The first is in
the bound variable list. The second is in initialization of the @t(DOLIST) 
variable. The third is in the @t(PRINT) expression. This program, which is
valid in current Common Lisp, would not be valid in a Common Lisp where 
functional and argument positions were evaluated in the same way. A common
thing to write instead would be:
@Begin(Example)
(DEFUN PRINT-SQRTS (LST)
  (DOLIST (ELEMENT LST)
    (PRINT (LIST ELEMENT (SQRT ELEMENT)))))
@End(Example)

As should be clear from these examples, the advantage of treating the function
and argument positions the same is that using parameters as functions is made
more syntactically convenient.

The disadvantage is that @i(not) using parameters as functions is made
syntactically less convenient since parameter names must be more
carefully chosen in order to not shadow the names of globally defined
functions which will be needed in the function body.

[My sense here is that this is what identifies the issue as essentially 
an axiomatic one and not one which can be proven (or disproven) as 
elegant/inelegant in some absolute terms. I'd like to work that in here
somehow. -KMP]

If you're looking for a very simple example of this phenomenon to discuss on 
a napkin over dinner, here it is:
@Begin(Example)
(DEFUN ODDITY-1 (LIST) (LIST LIST LIST))
(ODDITY #'CONS)
@End(Example)
Depending on which way the issue is decided, the possible return values from
this function are:
@Begin(Example)
(#<SUBR CONS> . #<SUBR CONS>)
(#<SUBR CONS> #<SUBR CONS>)
@End(Example)

@b(3.3 Number of Namespaces)

We shouldn't try to kid ourselves about the level of simplicity that will
be achieved by this change. Merging function cells and value cells doesn't
mean that every time you see a symbol, you can uniquely determine its 
meaning with no sense of context. Symbols will still have special meanings
when interpreted as types, declarations, etc.

@b(3.4 Macros and Name Collisions)

[I need to write lots more here, of course.]

Consider:

@Begin(Example)
(DEFMACRO MAKE-FOO (THINGS) `(LIST 'FOO THINGS))
...
(DEFUN FOO (LIST) (MAKE-FOO (CAR LIST)))
@End(Example)

or:

@Begin(Example)
(DEFMACRO FIRST (LIST) `(CAR ,LIST))
...
(DEFMACRO TEST-CAR (CAR TEST-LIST)
  (DO ((TESTS TEST-LIST (REST TESTS)))
      ((NULL TESTS))
    (FUNCALL (FIRST TESTS) CAR)))
@End(Example)

People have discussed, and IBM folks claim [I need to dig up a reference to this]
to have implemented, the ability to write:

@Begin(Example)
(DEFMACRO FIRST (LIST) `(',CAR ,LIST))
@End(Example)

This is syntactically more tedious and that would have to be weighed.
Nevertheless, it doesn't answer all technical problems. In particular,
their implementation works by getting the value of CAR at loadtime.
It doesn't address what happens if you do:

@Begin(Example)
(DEFMACRO FOO (N X) `(',(LAMBDA (X) (+ X N)) ,X))
(FOO 3 Z)
@End(Example)

since there is no function at loadtime to get. You have to output all
the code which supports the anonymous closure which the compiler finds
at runtime. This would have to be done recursively through all the functions
called by the indicated function, a problem which is recursively unsolvable
in general unless the entire compilation environment can be statically closed
over, which could be impossibly expensive in general.

@b(3.5 Space Efficiency)

If a name is used as both a variable and a function, it currently costs no
additional space. Any program which has symbols which are used to denote 
distinct functions and values, however, would have to be changed. In general,
this mean that some new symbols would be introduced. In most cases, the number
of new symbols introduced would not be extremely large, but there might be
pathological applications where there were exceptions.

Using the same name to refer to both a function and a value cell can be more
space efficient since it means adding only one additional cell to ...

Resolving the name conflicts that would result if functions
and variables were in the namespace would require the creation of additional
symbols.


@b(3.6 Time Efficiency)

In VAXLISP, the function cell is checked for call validity at SETF execution 
time to make sure that a jump to it without checking will be ok at call time.


@b(3.7 Cultural Compatibility)

We have encouraged the naming convention of *...* around global names.
To make functions and values the same would be to say that this convention
was then a somewhat gratuitous distinction.

@b(3.8 Special Variable Warnings)

Functions would want to be non-special, but would want to not be warned
about when used free. Normally, you have to declare variables SPECIAL to
get this behavior. This would result in lower error checking.

@b(3.9 Compatibility Issues)

Making a transition to a world with unified a function/value cell would
involve a considerable amount of incompatibility.

@b(3.9.1 Changing existing code)

Large bodies of code already exist which make assumptions about the current
semantics. That code would all have to be changed. Users who did not favor
this change would likely resent the amount of work required to make the 
change, which is not trivial.

In some cases, mechanical techniques could diagnose which programs needed
to be changed. However, because of the pervasive use of macros and of 
automatic programming techniques, it would not be possible to do such
diagnosis with 100% reliability in any automatic way.

@b(3.9.2 Compatibility packages)

Various compatibility schemes have been proposed which would allow these
problems to be hacked by compatibility packages ... [RPG: do you know what they
are? Steele was mentioning this idea to me but I didn't get the details. In
any case, I think the argument in the next paragraph will still apply if you can
expand this.]

The problem is that the compilers and other program-understanding programs
might be fooled by such compatibility things. For example, such programs
may have built-in assumptions about the function cell and value cell being
distinct and may not realize that a store into the value cell in one place
will perturb a later access to the function cell, which it may believe it has
proven could not be changed in a certain interval of code.

@b(3.10 Compatibility with Scheme)

Compatibility with Scheme is not currently a goal of the Common Lisp
design committee. On the other hand, if all other things are equal, there
would be no reason for us to seek to be gratuitously incompatible with
Scheme.

However, all other things are not equal. For example, there is an installed
base of code which would require changing. There are reasons to believe that
the change would not be gratuitous. 

Even if compatibility with Scheme was achieved on this point, there is
currently no iron-clad guarantee that Scheme will not later change in an
incompatible way that will thwart such a good faith move on the part of 
Common Lisp. It is an explicit goal of the Scheme designers [ref R↑3 Report]
that Common Lisp compatibility not be uppermost in the list of concerns.
That should weigh in.

@b(4. Summary)

[When we get close to done, perhaps we can do a quick one or two sentence
recap of the pros and cons [that word looks funny in lispy literature].]